package com.zhouchb.test;

import java.util.Arrays;

/**
 * @Author Zhouchb
 * @Create 2021-12-2021/12/29 :13:12
 * @Description
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,7,2,1,8,3};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] arr,int l,int r){
        if(l>=r){
            return;
        }
        int mid = partition(arr,l,r);
        sort(arr,l,mid-1);
        sort(arr,mid+1,r);
    }
    public static int partition(int[] arr,int l,int r){
        int key = arr[l];
        while (l<r){
            while (arr[r]>=key&&l<r){
                r--;
            }
                swap(arr,l,r);


            while (arr[l]<=key&&l<r){
                l++;
            }
                swap(arr,l,r);
        }
        arr[l]=key;
        return l;
    }
    public static void swap(int[] arr,int k,int j){
        int temp = arr[k];
        arr[k] = arr[j];
        arr[j] = temp;
    }

}
class SortTest{
    public static void main(String[] args) {
//        int[] arr = new int[]{6,5,9,0,1,1,2};
        int[] arr = new int[]{3,5,2,19,1,0,9,0};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] arr,int l,int r){
        if (l>=r){
            return;
        }
        int mid = patition(arr,l,r);
        sort(arr,l,mid-1);
        sort(arr,mid+1,r);
    }
    public static int patition(int[] arr,int l,int r){
        int temp = arr[l];
        while (l<r){
            while (arr[r]>=temp&&l<r){
                r--;
            }
            if (l<r){
                swap(arr,l,r);
            }
            while (arr[l]<=temp&&l<r){
                l++;
            }
            if (l<r){
                swap(arr,l,r);
            }
        }
    //    arr[l] = temp;
        return l;
    }
    public static void swap(int[] arr,int i,int k){
        int temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
}
//求10！
class 递归{
    public static void main(String[] args) {
        System.out.println(recursion(10));
    }
    public static int recursion(int num){
        if(num==1){
            return num;
        }
        return num*recursion(num-1);
    }
}

